package pri.zjy.dynamicProgramming;

/**
 * @author zhangjy
 * @description 回文子串
 * <p>
 * 给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
 * <p>
 * 回文字符串 是正着读和倒过来读一样的字符串。
 * <p>
 * 子字符串 是字符串中的由连续字符组成的一个序列。
 * @date 2025/6/15 17:02
 */
public class CountSubstrings_647 {

    public static void main(String[] args) {

    }

    /**
     * 参考dmsxl-dp
     * <p>
     * 分析：TODO
     * 1.dp数组如何定义？
     * <p>
     * 2.递推公式如何确定？
     * <p>
     * 3.遍历顺序如何确定？
     */
    public int countSubstrings(String s) {
        // 1.dp定义
        // dp[i][j]，表示[i, j]的子串是否回文
        int[][] dp = new int[s.length()][s.length()];
        // 2.递推
        // 若s[i]!=s[j]，则[i,j]必不可能是回文串，dp[i][j]=0;
        // 若s[i]==s[j]
        // 2.1.当j-i==0，表明i、j指向同一个字符，则是回文串，dp[i][j]=1;
        // 2.2.当j-i==1，表明i、j对应两个相邻字符，如aa，也是回文串，dp[i][j]=1;
        // 2.3.当j-i>1，需要根据dp[i+1][j-1]判断；相当于[0,3]要依据[1,2]判断一样，若[1,2]是回文串，且0、3对应字符相等，那么[0,3]也是回文串，即dp[i][j]=1;否则dp[i][j]=0
        // 3.初始化
        // 初始每个都不是回文子串（dp[][]=0），每个子串都要判断
        // 4.遍历顺序
        // 如果从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。
        // 所以，要从下到上（i=[s.length-1, 0]），从左到右遍历（j=[i, s.length-1]），这样保证dp[i + 1][j - 1]都是经过计算的。

        int count = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                if (s.charAt(i) != s.charAt(j)) {
                    // 一定不是回文子串
                    dp[i][j] = 0;
                } else {
                    // 可能是回文子串
                    if (j - i == 0) {
                        dp[i][j] = 1;
                        count++;
                    } else if (j - i == 1) {
                        dp[i][j] = 1;
                        count++;
                    } else {
                        // i、j之间还有子串，需要根据其最长的子串判断
                        if (dp[i + 1][j - 1] == 1) {
                            dp[i][j] = 1;
                            count++;
                        } else {
                            dp[i][j] = 0;
                        }
                    }
                }
            }
        }

        return count;
    }

}
